/**
 *
 */

export type IdType = number | string

export interface NodeAdapter<T> {
  getKey(t: T): IdType,

  //设置key的函数.
  setKey?: (t: T, key: IdType) => void,
  setParentKey?: (t: T, key: IdType) => void,

  addSub(parent: T, child: T),

  getSubs(parent: T): T[],

  rootId?: IdType,
}

export interface FromNodeAdapter<T> {
  getSubs(parent: T): T[],
}

export interface ToNodeAdapter<T> {
  getKey(t: T): IdType,

  //设置key的函数.
  setKey?: (t: T, key: IdType) => void,
  setParentKey?: (t: T, key: IdType) => void,

  addSub(parent: T, child: T),

  rootId?: IdType,
}

export interface TreeForEachAdapter<T> {
  getSubs(parent: T): T[],
}

export interface TreeTransformOption<F, T> {
  nodeAdapter_from: FromNodeAdapter<F>,
  nodeAdapter_to: ToNodeAdapter<T>,
  transformer: (F) => T
  //是否为T自动生成key
  autoGenerateKey: boolean
}

// export interface TreeTransformOption2<F, T> {
//   // F转换为T的函数
//   transformer: (F) => T
//   // 是否自动为T设置key
//   autoGenerateKey:boolean
// }

/**
 * 将一个Tree转化为另一个结构的tree
 * @param tree_from
 * @param o
 * @returns
 */

export function treeMap2<F, T>(tree_from: F[], o: TreeTransformOption<F, T>): T[] {
  const flatTree_from: F[] = [];
  treeForEach(tree_from, o.nodeAdapter_from, (n) => {
    flatTree_from.push(n);
  })
  const tree_to = flatTreeMap(flatTree_from, o);
  return tree_to;
}

export function flatTreeMap<F, T>(flatTree_from: F[], o: TreeTransformOption<F, T>): T[] {
  const flatTree_to: T[] = [];
  for (const t of flatTree_from) {
    const n = o.transformer(t);
    flatTree_to.push(n);
  }
  //转化为tree
  const tree2: T[] = [];
  for (const node_to of flatTree_to) {
    const parentId = o.nodeAdapter_to.getKey(node_to);
    if (parentId == o.nodeAdapter_to.rootId) {
      tree2.push(node_to);
      continue
    } else {
      const parent = flatTree_to.find((_node) => o.nodeAdapter_to.getKey(_node) == parentId)
      if (parent) {
        o.nodeAdapter_to.addSub(parent, node_to)
      }
    }
  }
  return tree2;
}


/**
 * 遍历的回调指定parent
 * @param tree
 * @param adapter
 * @param fn,
 * n:当前节点,parent:当前节点的parent
 * 所有节点都会被最为n,处理一次,顺序为PLR遍历
 * 当处理n时其parent是一定被处理过的
 */
export function treeForEach<T>(tree: T[], adapter: TreeForEachAdapter<T>, fn: (n: T, parent: T) => void) {
  for (let node of tree) {
    nodeForEach(node, undefined, adapter, fn);
  }
}

export function nodeForEach<T>(node: T, parent: T, adapter: TreeForEachAdapter<T>, fn: (n: T, parent: T) => void) {
  fn(node, parent)
  const subs = adapter.getSubs(node);
  for (let sub of subs) {
    nodeForEach(sub, node, adapter, fn);
  }
}

let nodeCount = 0;

function getKey(): number {
  nodeCount++;
  return nodeCount;
}

/**
 * 转换为其他类型的树节点
 * 1,没有parent的为根节点.
 * @param tree_from
 * @param o
 * @returns
 */

export function treeTransform<F, T>(tree_from: F[], o: TreeTransformOption<F, T>): T[] {
  const tree_to: T[] = [];
  const nodeMap: Map<F, T> = new Map<F, T>();
  treeForEach(tree_from, o.nodeAdapter_from, (n: F, parent: F) => {
    const node_to = o.transformer(n);
    if (o.autoGenerateKey) {
      o.nodeAdapter_to.setKey?.(node_to, getKey())
    }
    nodeMap.set(n, node_to);
    if (!parent) {
      //根节点
      o.nodeAdapter_to.setParentKey?.(node_to, o.nodeAdapter_to.rootId)
      tree_to.push(node_to);
    } else {
      //
      const node_toParent = nodeMap.get(parent);
      o.nodeAdapter_to.setParentKey?.(node_to, o.nodeAdapter_to.getKey(node_toParent))
      o.nodeAdapter_to.addSub(node_toParent, node_to)
    }
  })
  return tree_to;
}

export function treeFind<T>(tree: T[], adapter: TreeForEachAdapter<T>, findFn: (node: T) => boolean): T | undefined {
  for (const node of tree) {
    if (findFn(node)) {
      return node;
    } else {
      const subs = adapter.getSubs(node);
      const target = treeFind(subs, adapter, findFn)
      if (target) {
        return target
      }
    }
  }
  return undefined;
}